package ru.usu.gv.gui.clustering;

import ru.usu.gv.graph.Graph;
import ru.usu.gv.graph.Vertex;
import ru.usu.gv.utils.exports.GraphExporter;
import ru.usu.gv.utils.generators.ClusterGenerator;

/**
 * @author spupyrev
 * 17.11.2008
 * 
 * See details in 
 * "Fast unfolding of communities in large networks" (Vincent D. Blondel et.al.)
 */
public class ClusterHierarchyBuilder
{
	private static final double PRECISION = 1e-6;
	private static final int display_level = -2;

	public Cluster buildHierarchy(Graph graph)
	{
		System.out.println("start");
		long startTime = System.currentTimeMillis();

		BinaryGraph binaryGraph = new BinaryGraph(graph);

		Cluster rootCluster = new Cluster(binaryGraph);
		for (int i = 0; i < graph.getSize(); i++)
		{
			Vertex v = graph.getVertex(i);
			rootCluster.addVertex(v);
		}

		Community c = new Community(binaryGraph, -1, PRECISION);

		double modularity;
		double new_mod = c.modularity();
		int level = -1;

		do
		{
			modularity = new_mod;

			Object[] res = doStep(c, binaryGraph, modularity, level, rootCluster);
			binaryGraph = (BinaryGraph) res[0];
			new_mod = (Double) res[1];
			level = (Integer) res[2];
			rootCluster = (Cluster) res[3];

			c = new Community(binaryGraph, -1, PRECISION);
		} while (new_mod - modularity > PRECISION);

		long endTime = System.currentTimeMillis();
		System.out.println("Discovering done(precisiion=" + PRECISION + "): modularity = " + new_mod + " execution time = " + (endTime - startTime) / 1000.0 + " sec.");

		postProcessClusters(rootCluster);
		rootCluster.postInit(0);

		return rootCluster;
	}

	//Order:
	//graph
	//newmodularity
	//level
	//rootCluster
	private Object[] doStep(Community c, BinaryGraph g, double modularity, int level, Cluster rootCluster)
	{
		System.out.println("");
		System.out.println("network: " + g.n + " nodes, " + g.totalWeight + " weight");

		double newModularity = c.one_level();

		System.out.println("communities computed");
		System.out.println("modularity increased from " + modularity + " to " + newModularity);

		if (display_level == -1)
			c.display_partition();

		g = c.partition2graph_binary();
		rootCluster = c.prepareCluster(rootCluster, g);

		level++;

		if (level == display_level)
			g.display();

		System.out.println("network of communities computed");
		return new Object[] { g, newModularity, level, rootCluster };
	}

	//remove stub(==with one child) subclusters
	private void postProcessClusters(Cluster cluster)
	{
		if (cluster.containsVertexes())
			return;

		if (cluster.getSubClusters().size() == 1)
		{
			Cluster subCluster = cluster.getSubClusters().get(0);
			cluster.init(subCluster.getSubClusters(), subCluster.getVertexes(), subCluster.getBinaryGraph());
			postProcessClusters(cluster);
		}
		else
		{
			for (Cluster subCluster : cluster.getSubClusters())
			{
				postProcessClusters(subCluster);
			}
		}
	}

	public static void main(String argc[])
	{
		Graph graph = ClusterGenerator.generateGraph();
		GraphExporter.exportAsLJGraph(graph, System.out);

		ClusterHierarchyBuilder builder = new ClusterHierarchyBuilder();
		Cluster rootCluster = builder.buildHierarchy(graph);
		System.out.println(rootCluster);
	}
}
